/*
 *https://leetcode.cn/problems/longest-palindromic-substring/
 *96. 不同的二叉搜索树
 *medium 吴朝泽 2024.10.15
 *区间DP
*/

class Solution {
public:
    int numTrees(int n) {
        // 用于存储不同节点数的二叉搜索树的数量
        vector<int> f(n + 1);
        f[0] = 1; // 当节点数为 0 时，只有一种空树

        // i 表示当前节点的数量，从 1 到 n
        for (int i = 1; i <= n; ++i) {
            // j 表示当前根节点的位置，j 从 0 到 i-1，表示选择不同的根节点
            for (int j = 0; j < i; ++j) {
                // f[i] 是由 j 作为根节点时的左子树和右子树组合而成的
                // 左子树节点数为 j，右子树节点数为 i - j - 1
                // f[j] * f[i - j - 1] 代表选择 j 作为根时的组合方式
                f[i] += f[j] * f[i - j - 1];
            }
        }
        return f[n];
    }
};
